package org.example.struct.array2;

import java.util.*;

/**
 * @author liyishan
 * @date 2024/7/22 09:56
 * @apiNote
 */

public class Test02101MaximumDetonation {

    public int maximumDetonation(int[][] bombs) {
        int n = bombs.length;
        Map<Integer, List<Integer>> edges = new HashMap<>();
        for(int i =0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(i !=j && isConnected(bombs,i,j)){
                    edges.putIfAbsent(i,new ArrayList<>());
                    edges.get(i).add(j);
                }
            }
        }
        int res =0;
        for(int i =0;i<n;i++){
            boolean[] visited = new boolean[n];
            int cnt =1;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(i);
            visited[i] = true;
            while(!queue.isEmpty()){
                int cur = queue.poll();
                for(int next : edges.getOrDefault(cur,new ArrayList<>())){
                    if(visited[next]){
                        continue;
                    }
                    cnt++;
                    queue.offer(next);
                    visited[next] = true;
                }
            }
            res = Math.max(res,cnt);
        }
        return res;
    }

    public boolean isConnected(int[][] bombs,int u ,int v){
        long dx = bombs[u][0]  - bombs[v][0];
        long dy = bombs[u][1]  - bombs[v][1];
        return (long)bombs[u][2] * bombs[u][2] >= dx * dx + dy * dy;
    }
}
